package 动态规划;

import java.util.Arrays;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 最长上升子序列.java
 * @Description TODO
 * @createTime 2020年11月14日 18:56:00
 * 给定一个无序的整数数组，找到其中最长上升子序列的长度。
 *
 * 示例:
 *
 * 输入: [10,9,2,5,3,7,101,18]
 * 输出: 4
 * 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
 *
 * 思路：动态规划是 当前问题可以通过拆分成子问题来解决
 * 动态规划应用于子问题重合的情况，不同的子问题具有相同的子子问题，
 *
 * 动态规划算法将每个子问题求解一次，将其解保存在一个表格中，需要时进行调用。
 *dp[i]=max{dp[i],dp[j]+1}  这题为什么前面是dp[i]
 */
public class 最长上升子序列 {
    class Solution {
        public int lengthOfLIS(int[] nums) {
            int n = nums.length;
            //定义dp数组，dp数组中的每个值存放着对应nums数组中每个位置的最长上升子序列
            int[] dp = new int[n];
            //每个位置的最长上升子序列最小也为1，即他自身（比如递减序列），可以填充为1
            Arrays.fill(dp, 1);
            //求nums中的每个位置的最长上升子序列，将值放到对应位置处的dp数组中
            for(int i = 0; i < nums.length; ++i){
                //状态转移方程
                for(int j = 0; j < i; ++j){
                    //如果前面有小于nums[i]的数，那么就令当前dp[i] = dp[j] + 1，因为有多钟组合，我们取最大的一组值放到dp[i]中
                    if(nums[j] < nums[i]){
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
            }

            //最终得到的dp数组就是每个位置的最长上升子序列的值，我们求出最大值就是该答案的解
            int res = 0;
            for(int k = 0; k < dp.length; k++){
                res = Math.max(res, dp[k]);
            }
            return res;
        }
    }
}
